package newone;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTreeNode {
    private BTnode root=null;
    public BinaryTreeNode(){
        root=new BTnode(1,"rootNode(A)");
    }

    public void createBinTree(BTnode root){
        BTnode newNodeB = new BTnode(2,"B");
        BTnode newNodeC = new BTnode(3,"C");
        BTnode newNodeD = new BTnode(4,"D");
        BTnode newNodeE = new BTnode(5,"E");
        BTnode newNodeF = new BTnode(6,"F");
        root.leftChild=newNodeB;
        root.rightChild=newNodeE;
        root.leftChild.rightChild=newNodeC;
        root.rightChild.rightChild=newNodeF;
        root.leftChild.rightChild.leftChild=newNodeD;
    }
    public boolean isEmpty(){
        return root==null;
    }

    //树的高度
    public int height(){
        return height(root);
    }

    //节点个数
    public int size(){
        return size(root);
    }


    private int height(BTnode subTree){
        if(subTree==null)
            return 0;
        else{
            int i=height(subTree.leftChild);
            int j=height(subTree.rightChild);
            return (i<j)?(j+1):(i+1);
        }
    }
    private int size(BTnode subTree){
        if(subTree==null){
            return 0;
        }else{
            return 1+size(subTree.leftChild)
                    +size(subTree.rightChild);
        }
    }

    public BTnode parent(BTnode element){
        return (root==null|| root==element)?null:parent(root, element);
    }

    public BTnode parent(BTnode subTree,BTnode element){
        if(subTree==null)
            return null;
        if(subTree.leftChild==element||subTree.rightChild==element)
            return subTree;
        BTnode p;
        if((p=parent(subTree.leftChild, element))!=null)
            return p;
        else
            return parent(subTree.rightChild, element);
    }
    public BTnode getLeftChildNode(BTnode element){
        return (element!=null)?element.leftChild:null;
    }
    public BTnode getRightChildNode(BTnode element){
        return (element!=null)?element.rightChild:null;
    }
    public BTnode getRoot(){
        return root;
    }
    public void destroy(BTnode subTree){
        if(subTree!=null){
            destroy(subTree.leftChild);
            destroy(subTree.rightChild);
            subTree=null;
        }
    }
    public void traverse(BTnode subTree){
        System.out.println("key:"+subTree.key+"--name:"+subTree.data);;
        traverse(subTree.leftChild);
        traverse(subTree.rightChild);
    }

    //前序遍历
    public void preOrder(BTnode subTree){
        if(subTree!=null){
            visted(subTree);
            preOrder(subTree.leftChild);
            preOrder(subTree.rightChild);
        }
    }

    //中序遍历
    public void inOrder(BTnode subTree){
        if(subTree!=null){
            inOrder(subTree.leftChild);
            visted(subTree);
            inOrder(subTree.rightChild);
        }
    }

    //后序遍历
    public void postOrder(BTnode subTree) {
        if (subTree != null) {
            postOrder(subTree.leftChild);
            postOrder(subTree.rightChild);
            visted(subTree);
        }
    }

    //前序遍历的非递归实现
    public void nonRecPreOrder(BTnode p){
        Stack<BTnode> stack=new Stack<BTnode>();
        BTnode node=p;
        while(node!=null||stack.size()>0){
            while(node!=null){
                visted(node);
                stack.push(node);
                node=node.leftChild;
            }
            if(stack.size()>0){
                node=stack.pop();
                node=node.rightChild;
            }
        }
    }
    public void preTraversal(BTnode p ){
        Stack<BTnode>  a = new Stack<BTnode>();
        a.push(p);
        BTnode t;
        while( !a.isEmpty() ){
            t = a.pop();
            while( t!=null){
                System.out.println(t.data);
                if(t.rightChild!=null)
                {a.push(t.rightChild);}
                t = t.leftChild;
            }
        }
    }

    //中序遍历的非递归实现
    public void nonRecInOrder(BTnode p){
        Stack<BTnode> stack =new Stack<BTnode>();
        BTnode node =p;
        while(node!=null||stack.size()>0){
            while(node!=null){
                stack.push(node);
                node=node.leftChild;

            }
            if(stack.size()>0){
                node=stack.pop();
                visted(node);
                node=node.rightChild;
            }
        }
    }

    //后序遍历的非递归实现
    public void noRecPostOrder(BTnode p){
        Stack<BTnode> stack=new Stack<BTnode>();
        BTnode node =p;
        while(p!=null){
            for(;p.leftChild!=null;p=p.leftChild){
                stack.push(p);
            }
            while(p!=null&&(p.rightChild==null||p.rightChild==node)){
                visted(p);
                node =p;
                if(stack.empty())
                    return;
                p=stack.pop();
            }
            stack.push(p);
            p=p.rightChild;
        }
    }
    public void visted(BTnode subTree){
        subTree.isVisted=true;
        System.out.println("key:"+subTree.key+"--name:"+subTree.data);;
    }

    //层次遍历
    public void levelIterator(BTnode n){
        Queue<BTnode> queue = new LinkedList<BTnode>();
        queue.offer(n);
        while (!queue.isEmpty()) {
            BTnode t = queue.poll();
            if (t !=null) {
                visted(t);
            }
            if (t.leftChild !=null) {
                queue.offer(t.leftChild);
            }
            if (t.rightChild !=null) {
                queue.offer(t.rightChild);
            }
        }
    }
    //测试
    public static void main(String[] args) {
        BinaryTreeNode bt = new BinaryTreeNode();
        bt.createBinTree(bt.root);
        System.out.println("the size of the tree is " + bt.size());
        System.out.println("the height of the tree is " + bt.height());
        System.out.println("前序遍历：");
        bt.preOrder(bt.root);
        System.out.println("中序遍历：");
        bt.inOrder(bt.root);
        System.out.println("后序遍历：");
        bt.postOrder(bt.root);
        System.out.println("非递归实现前序遍历：");
        bt.nonRecPreOrder(bt.root);
        bt.preTraversal(bt.root);
        System.out.println("层次遍历：");
        bt.levelIterator(bt.root);
        System.out.println("非递归实现中序遍历：");
        bt.nonRecInOrder(bt.root);
        System.out.println("非递归实现后序遍历：");
        bt.noRecPostOrder(bt.root);
    }
}
